package 选择排序;

import java.util.Arrays;

public class 选择排序 {

	public static void main(String[] args) {
//		int[] arr = {5,2,1,4,3};
//		selectSort(arr);
//		System.out.println(Arrays.toString(arr));
		
		
		int[] longInt = new int[80000];
		for (int i = 0; i < longInt.length; i++) {
			longInt[i] = (int) (Math.random()*10000);
		}
		
		//时间复杂度和冒泡一样，O(n^2)，但是速度快很多，13s ：1s
		
		long star = System.currentTimeMillis();
		selectSort(longInt);
		long end = System.currentTimeMillis();
		System.out.println((end-star) + "毫秒");
		System.out.println((end-star)/1000 + "秒");//1s
		
		
		
	}
	
	/**
	 * 选择排序，O(n^2)
	 * @param arr
	 */
	public static void selectSort(int[] arr) {
		
		//一共交换 length-1 次
		for(int i = 0 ; i < arr.length-1 ; i++) {
			//首先选择最小值，与 arr[0] 交换，再从剩下值中选择最小值，与arr[1] 交换
			
			//假设最小值就是 正在循环的 i ，因为前面的值都拍好序了。
			int min = arr[i];
			int index = i;
			
			//注意前面的值都排好序了，从 i + 1 开始
			for(int j = i + 1 ; j < arr.length ; j++) {
				if(min > arr[j]) {
					min = arr[j];
					index = j;
				}
			}
			
			//交换 当前值 与 最小值
			//如果i正好是最小值，就不交换了，因为顺序没错
			if(index != i) {
				arr[index] = arr[i];
				arr[i] = min;
			}
			
		}
		
	}
}
